\documentclass{beamer}

\mode<presentation>
{
  \usetheme{Antibes}
  \setbeamercovered{transparent}
}

\usepackage{hyperref}
\usepackage{amsmath,amsthm,amssymb}
\usepackage[portuguese]{babel}
\usepackage[utf8]{inputenc}
\usepackage{multirow}
\usepackage{times}

\title[Trabalho 2]
{Trabalho 2}

\subtitle
{Desempenho de algoritmos paralelos para encontrar palíndromos}

\author
{Filipe~Neto \and Rommel~Cruz \and Samuel~Fadel}

\institute[Universidade de São Paulo]
{
  Instituto de Ciências Matemáticas e de Computação\\
  Universidade de São Paulo
}

\date[2013]
{SSC0143 -- Programação Concorrente, 2013}

\subject{Trabalho 2}

% \pgfdeclareimage[height=0.5cm]{university-logo}{university-logo-filename}
% \logo{\pgfuseimage{university-logo}}

%\AtBeginSection[]
%{
%  \begin{frame}<beamer>{Tópicos}
%    \tableofcontents[currentsection,currentsubsection]
%  \end{frame}
%}


\begin{document}

\maketitle

\section{Objetivos}
\begin{frame}{Objetivos}
  Desenvolver algoritmos paralelos, usando OpenMP~\cite{OpenMP} e
  MPI~\cite{MPI}, para encontrar palíndromos
  \begin{itemize}
  \item
    Texto pequeno
    \begin{itemize}
      \item Encontrar palavras palíndromas
      \item Encontrar frases palíndromas (considerando somente letras e
            números)
    \end{itemize}
  \item
    Texto grande
    \begin{itemize}
      \item Encontrar palavras palíndromas
      \item Determinar se a soma de seus caracteres é um número primo
    \end{itemize}
  \end{itemize}
\end{frame}

\section{Soluções}
\subsection{Texto pequeno}
\begin{frame}
  Processo \textbf{root}
  \begin{itemize}
    \item Responsável por pré-processar o texto
    \item Divide o texto pré-processado
    \begin{itemize}
      \item O texto não pode ser quebrado no meio de palavras
    \end{itemize}
    \item Envia as partes a todos os processos (inclusive o próprio
    \textbf{root})
  \end{itemize}
\end{frame}

\begin{frame}
  Cada processo
  \begin{itemize}
    \item Procura palíndromos em seu trecho
    \begin{itemize}
      \item Trecho determinado pelo \emph{rank}
    \end{itemize}
    \item Tanto palavras quanto frases
  \end{itemize}
\end{frame}

\begin{frame}{}
  \begin{figure}[h]
    \centering
    \includegraphics[width=0.8\linewidth]{img/small.pdf}
  \end{figure}
  \begin{figure}[h]
    \centering
    \includegraphics[width=0.8\linewidth]{img/small-par.pdf}
  \end{figure}
\end{frame}

\subsection{Texto grande}
\begin{frame}{Dividir e conquistar}
  Processo \textbf{root}
  \begin{itemize}
    \item Preprocessa o texto utilizando um pipeline
    \begin{itemize}
      \item Minúsculas e caracteres especiais
      \item Encontra começo e fim das palavras
      \item Envia palavras não repetidas utilizando AVL
    \end{itemize}
  \end{itemize}
\end{frame}

\subsection{Texto grande}
\begin{frame}{Dividir e conquistar}
  Demais processos
  \begin{itemize}
    \item Calculam o crivo de Eratóstenes
    \item Recebem as palavras
    \item Verificam se é palíndromo
    \item Calculam a soma dos caracteres e verificam se é primo
  \end{itemize}
\end{frame}

\begin{frame}{Dividir e conquistar}
  \begin{figure}[h]
    \centering
    \includegraphics[width=0.8\linewidth]{img/large-dnc.pdf}
  \end{figure}
\end{frame}

\begin{frame}{Decomposição de dados}
  Processo \textbf{root}
  \begin{itemize}
    \item Responsável por pré-processar o texto
    \item Divide o texto pré-processado
    \begin{itemize}
      \item O texto não pode ser quebrado no meio de palavras
    \end{itemize}
    \item Envia as partes aos demais processos
    \item Após envio, executa o crivo de Eratóstenes
  \end{itemize}
\end{frame}

\begin{frame}{Decomposição de dados}
  Demais processos
  \begin{itemize}
    \item Quebra a parte que recebeu em palavras
    \begin{itemize}
      \item Sequências de caracteres e números contíguos -- sem espaço em branco
    \end{itemize}
    \item Envia palíndromos com tamanho maior ou igual a 3 para o processo
          \textbf{root}
  \end{itemize}
\end{frame}

\begin{frame}{Decomposição de dados}
  De volta ao \textbf{root}
  \begin{itemize}
    \item Recebe os palíndromos e armazena em uma árvore binária
    \begin{itemize}
      \item Eficiente ($O(\log n)$) para encontrar palavras repetidas
    \end{itemize}
    \item Para cada palíndromo, calcula a soma de seus caracteres
    \item Determina se a soma é um número primo, usando os primos calculados com
    o crivo de Eratóstenes
  \end{itemize}
\end{frame}

\begin{frame}{Decomposição de dados}
  \begin{figure}[h]
    \centering
    \includegraphics[width=0.8\linewidth]{img/large-dd.pdf}
  \end{figure}
\end{frame}

\section{Resultados}
\subsection{Texto pequeno}
\begin{frame}
  \tiny
  \begin{table}[h]
    \centering
    \begin{tabular}{ c c c c c c}
        \hline
        T. Sequencial (ms) & N. Processos & T. Paralelo$^1$ (ms) & Speedup$^1$ & T. Paralelo$^2$ (ms) & Speedup$^2$ \\ \hline
        \hline
        \multirow{4}{*}{170$\pm$4} & 2 &  204$\pm$1  & 0.83 &  915$\pm$73  & 0.19 \\
                                   & 3 &  174$\pm$13 & 0.97 & 1080$\pm$142 & 0.16 \\
                                   & 4 &  204$\pm$9  & 0.83 & 1466$\pm$70  & 0.12 \\
                                   & 5 & 1206$\pm$11 & 0.14 & 1433$\pm$73  & 0.12 \\ \hline
    \end{tabular}
  \end{table}
\end{frame}

\begin{frame}
  \begin{figure}[h]
    \centering
    \includegraphics[width=0.9\linewidth]{img/small-tempos.pdf}
  \end{figure}
\end{frame}

\subsection{Texto grande}
\begin{frame}
  \tiny
  \begin{table}[h]
    \centering
    \begin{tabular}{ c c c c c c}
        \hline
        T. Sequencial (ms) & N. Processos & T. Paralelo$^1$ (ms) & Speedup$^1$ & T. Paralelo$^2$ (ms) & Speedup$^2$ \\ \hline
        \hline
        \multirow{4}{*}{379$\pm$14} & 2 &  8767$\pm$1176  & 0.04 & 12968$\pm$925   & 0.03 \\
                                    & 3 &  8812$\pm$198   & 0.04 & 13743$\pm$2012  & 0.03 \\
                                    & 4 &  9156$\pm$103   & 0.04 & 13105$\pm$472   & 0.03 \\
                                    & 5 & 11442$\pm$392   & 0.03 & 14040$\pm$1257  & 0.03 \\ \hline
    \end{tabular}
  \end{table}
  \begin{table}[h]
    \centering
    \begin{tabular}{ c c c c c c}
        \hline
        T. Sequencial (ms) & N. Processos & T. Paralelo$^1$ (ms) & Speedup$^1$ & T. Paralelo$^2$ (ms) & Speedup$^2$ \\ \hline
        \hline
        \multirow{4}{*}{379$\pm$14} & 2 & 1083$\pm$12 & 0.35 & 2314$\pm$62  & 0.16 \\
                                    & 3 &  761$\pm$26 & 0.50 & 2162$\pm$207 & 0.18 \\
                                    & 4 &  666$\pm$42 & 0.57 & 2281$\pm$87  & 0.17 \\
                                    & 5 & 1653$\pm$6  & 0.23 & 2237$\pm$126 & 0.17 \\ \hline
    \end{tabular}
  \end{table}
\end{frame}

\begin{frame}{Dividir e conquistar}
  \begin{figure}[h]
    \centering
    \includegraphics[width=0.9\linewidth]{img/large-dnc-tempos.pdf}
  \end{figure}
\end{frame}

\begin{frame}{Decomposição de dados}
  \begin{figure}[h]
    \centering
    \includegraphics[width=0.9\linewidth]{img/large-dd-tempos.pdf}
  \end{figure}
\end{frame}

\section*{Bibliografia e Referências}
\begin{frame}{Bibliografia e Referências}
  \begin{thebibliography}{9}
  \bibitem{OpenMP}
  OpenMP \\ \url{http://www.openmp.org/}
  \bibitem{MPI}
  MPI \\ \url{http://www.mcs.anl.gov/mpi/}
  \end{thebibliography}
\end{frame}

\end{document}
